In a memory system using a nonvolatile memory, such as a NAND flash memory, a physical erase unit (hereafter referred to as the “erase block”) is very large relative to the smallest unit of data that can be accessed from a host. Also, in response to a request to overwrite, physical data erasing is not performed and a writing control method which records new data in a different physical address area of the nonvolatile memory is adopted. If overwriting is repeated in this manner, the block containing invalid data will increase and the areas available for newly written data will decrease. Therefore, a compaction (garbage collection) processing is performed to free up areas available for new writes.
Generally, in a memory system, the locations of valid data are held in an effective data map, and this effective data map is searched for the valid data during the compaction processing. However, an exclusive memory area for holding this effective data map is required, and the size of this area increases in proportion to the capacity of the NAND flash memory installed in a memory system.